{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Palindromic Subsequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPalindromes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计回文子序列数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你数字字符串&nbsp;<code>s</code>&nbsp;，请你返回&nbsp;<code>s</code>&nbsp;中长度为&nbsp;<code>5</code>&nbsp;的 <b>回文子序列</b>&nbsp;数目。由于答案可能很大，请你将答案对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果一个字符串从前往后和从后往前读相同，那么它是 <strong>回文字符串</strong>&nbsp;。</li>\n",
    "\t<li>子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = \"103301\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "总共有 6 长度为 5 的子序列：\"10330\" ，\"10331\" ，\"10301\" ，\"10301\" ，\"13301\" ，\"03301\" 。\n",
    "它们中有两个（都是 \"10301\"）是回文的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"0000000\"\n",
    "<b>输出：</b>21\n",
    "<b>解释：</b>所有 21 个长度为 5 的子序列都是 \"00000\" ，都是回文的。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"9999900000\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>仅有的两个回文子序列是 \"99999\" 和 \"00000\" 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含数字字符。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-palindromic-subsequences](https://leetcode.cn/problems/count-palindromic-subsequences/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-palindromic-subsequences](https://leetcode.cn/problems/count-palindromic-subsequences/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"103301\"', '\"0000000\"', '\"9999900000\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c \n",
    "            suf[d] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c \n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c \n",
    "            pre[d] += 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        # 规定长度为 5\n",
    "        # 我们要统计一个规定数目的回文子序列\n",
    "        # 统计回文子序列的技巧 ---- 枚举中间的那个数\n",
    "        # 对于这道题目来说，因为是 5 个数 ---- 从中间的那个数开始\n",
    "        # 从左往右 和 从右往左 应该要都对应同一个数字，那么我们就只需要统计 从左往右 和 从右往左\n",
    "        # 有多少个满足条件的数字组合 相乘即可   12 5 21\n",
    "\n",
    "        # 统计 中间数的 右边 有多少满足条件的数组\n",
    "        surf = [0] * 10\n",
    "        surf2 = [0] * 100\n",
    "        for i in map(int, reversed(s)):\n",
    "            for j, v in enumerate(surf):\n",
    "                surf2[i*10 + j] += v\n",
    "            surf[i] += 1  # i 在完成十位的任务后就要加到个位的候选上\n",
    "        \n",
    "        # 后缀处理完毕后就要开始处理前缀\n",
    "        # 我们可以把答案计算过程和前缀的处理结合起来\n",
    "        res = 0\n",
    "        pre = [0] * 10 \n",
    "        pre2 = [0] * 100\n",
    "        for i in map(int, s):\n",
    "            # 因为枚举的 i 是中间项，那么是不能算到后缀里面的，因此要除去\n",
    "            surf[i] -= 1\n",
    "            for j, v in enumerate(surf):\n",
    "                surf2[i * 10 + j] -= v\n",
    "            # 此时 surf2 和 pre2 中的就是当前的答案\n",
    "            res += sum(c1*c2 for c1, c2 in zip(pre2, surf2))\n",
    "            # 再把当前的i加到前缀里面\n",
    "            for j, v in enumerate(pre):\n",
    "                pre2[i * 10 + j] += v\n",
    "            pre[i] += 1\n",
    "        return res % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "\n",
    "        for v in map(int, reversed(s)):\n",
    "            for j in range(10):\n",
    "                suf2[j +v * 10] += suf[j]\n",
    "            suf[v]+= 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0]*10\n",
    "        pre2= [0]  * 100\n",
    "        for v in map(int, s):\n",
    "            suf[v] -= 1;\n",
    "            for j in range(10):\n",
    "                suf2[j +v * 10] -= suf[j]\n",
    "            ans += sum(c1* c2 for c1, c2 in zip(pre2, suf2))\n",
    "            for j in range(10):\n",
    "                pre2[j +v * 10] += pre[j]\n",
    "            pre[v]+= 1\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        def isPalindrome(s_sub):\n",
    "            if s_sub[0] == s_sub[-1] and s_sub[1] == s_sub[-2]:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        mod = 10 ** 9 + 7\n",
    "        if len(s) < 5:\n",
    "            return 0\n",
    "        \n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j,c in enumerate(suf):\n",
    "                suf2[d*10+j] += c\n",
    "            suf[d] += 1\n",
    "        \n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        ans = 0\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j,c in enumerate(suf):\n",
    "                suf2[d*10+j] -= c\n",
    "            ans += sum(c1*c2 for c1,c2 in zip(suf2,pre2))\n",
    "            for j,c in enumerate(pre):\n",
    "                pre2[d*10+j] += c\n",
    "            pre[d] += 1\n",
    "        return ans%(10**9+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        suf = [0]*10 # 已经出现的各个数字的次数\n",
    "        suf2 = [0]*100 # 已经出现的d,c数对\n",
    "        for d in map(int, s[::-1]):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d*10+j] += c\n",
    "            suf[d] += 1\n",
    "        ans = 0\n",
    "        pre = [0]*10\n",
    "        pre2 = [0]*100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d*10+j] -= c\n",
    "            ans += sum(c1*c2 for c1, c2 in zip(pre2, suf2)) # 以当前的d为中心 前面和后面的数对可以构成回文\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d*10+j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10**9+7)\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/count-palindromic-subsequences/solutions/1993115/qian-hou-zhui-fen-jie-o100-chang-shu-kon-51cv/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        # 长度为5，回文子序列。\n",
    "        # 然后找中间有几个长度为3的。然后找中间有几个长度为1的。\n",
    "        n = len(s)\n",
    "        pre = [0]*10\n",
    "        pre2 = [0]*100\n",
    "        for i in range(n):\n",
    "            c = int(s[i])\n",
    "            if i:\n",
    "                for j in range(10):\n",
    "                    pre2[j*10+c] += pre[j]\n",
    "            pre[c] += 1\n",
    "\n",
    "        suf = [0]*10\n",
    "        suf2 = [0]*100\n",
    "        ans = 0\n",
    "        m = 1e9+7\n",
    "        for i in range(n-1, 1, -1):\n",
    "            c = int(s[i])\n",
    "            pre[c] -= 1\n",
    "            for j in range(10):\n",
    "                pre2[j*10+c] -= pre[j]\n",
    "\n",
    "            if i == n-1:\n",
    "                suf[c] += 1\n",
    "                continue\n",
    "\n",
    "            for t in range(100):\n",
    "                ans = (ans%m + pre2[t]*suf2[t])%m\n",
    "\n",
    "            for j in range(10):\n",
    "                suf2[j*10+c] += suf[j]\n",
    "            suf[c] += 1\n",
    "\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        single_digit_suffix_count = [0] * 10\n",
    "        double_digit_suffix_count = [0] * 100\n",
    "\n",
    "        # Populate suffix counts for single and double digits\n",
    "        for digit in map(int, reversed(s)):\n",
    "            for j in range(10):\n",
    "                double_digit_suffix_count[j + digit * 10] += single_digit_suffix_count[j]\n",
    "            single_digit_suffix_count[digit] += 1\n",
    "\n",
    "        result = 0\n",
    "        single_digit_prefix_count = [0]*10\n",
    "        double_digit_prefix_count = [0]  * 100\n",
    "\n",
    "        # For each character in s\n",
    "        for digit in map(int, s):\n",
    "            single_digit_suffix_count[digit] -= 1\n",
    "            for j in range(10):\n",
    "                double_digit_suffix_count[j + digit * 10] -= single_digit_suffix_count[j]\n",
    "            \n",
    "            # Checking for palindromic subsequences using prefix and suffix counts\n",
    "            result += sum(count1 * count2 for count1, count2 in zip(double_digit_prefix_count, double_digit_suffix_count))\n",
    "            \n",
    "            for j in range(10):\n",
    "                double_digit_prefix_count[j + digit * 10] += single_digit_prefix_count[j]\n",
    "            single_digit_prefix_count[digit] += 1\n",
    "        \n",
    "        return result % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, s[::-1]): #(d, 中心点, d)\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d*10+j] += c \n",
    "            suf[d] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d*10+j] -= c #撤销\n",
    "            \n",
    "            ans += sum([c1*c2 for c1, c2 in zip(pre2, suf2)])\n",
    "\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d*10+j] += c \n",
    "            pre[d] += 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "前后缀分解，没有立刻反应过来，可以理解，毕竟这种题做得不多，代码也打得少\n",
    "不过以后就不能再反应这么慢了\n",
    "'''\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        #前后缀分解代码\n",
    "        suf=[0]*10\n",
    "        suf2=[0]*100\n",
    "        for d in map(int,s[::-1]):\n",
    "            for j,c in enumerate(suf):\n",
    "                #仍然是d*10，分清楚谁先谁后\n",
    "                suf2[d*10+j]+=c\n",
    "            suf[d]+=1\n",
    "        pre=[0]*10\n",
    "        pre2=[0]*100\n",
    "        #接下来就可以一边遍历，一边计算了\n",
    "        ans=0\n",
    "        for x in map(int,s):\n",
    "            suf[x]-=1 #放在前面是因为同一个数不能被选两次,先把它从后缀表中移除\n",
    "            for j,c in enumerate(suf):\n",
    "                suf2[x*10+j]-=c   \n",
    "            #这其实有个小技巧，因为我们是用下标来代表(d1,d2)的 \n",
    "            for c1,c2 in zip(pre2,suf2):\n",
    "                ans+=c1*c2\n",
    "            #注意，这边要反过来\n",
    "            for j,c in enumerate(pre):\n",
    "                pre2[x*10+j]+=c\n",
    "            pre[x]+=1\n",
    "        return ans % (10**9+7)\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#返回 s 中长度为 5 的 回文子序列 数目\n",
    "#输入：s = \"103301\"输出：2；输入：s = \"9999900000\"输出：2\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        #前后缀，然后枚举每个位置作为回文中心，向两边拓展\n",
    "        sufix,sufix2=[0]*10,[0]*100 #分别统计每个字符出现的位置与组合a,b出现的位置\n",
    "        for d in map(int,reversed(s)):\n",
    "            for j,c in enumerate(sufix):\n",
    "                sufix2[d*10+j]+=c\n",
    "            sufix[d]+=1\n",
    "        ans=0\n",
    "        prefix,prefix2=[0]*10,[0]*100\n",
    "        for d in map(int,s):\n",
    "            sufix[d]-=1\n",
    "            for j,c in enumerate(sufix):\n",
    "                sufix2[d*10+j]-=c#撤销\n",
    "            ans+=sum(c1*c2 for c1,c2 in zip(prefix2,sufix2))#枚举所有字符组合\n",
    "            for j,c in enumerate(prefix):\n",
    "                prefix2[d*10+j]+=c \n",
    "            prefix[d]+=1\n",
    "        return ans%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c \n",
    "            suf[d] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c \n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c \n",
    "            pre[d] += 1\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        leftCnt = [0] * 10 \n",
    "        left = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(n):\n",
    "            v1 = ord(s[i]) - ord('0')\n",
    "            for v2 in range(10):\n",
    "                left[v2][v1] += leftCnt[v2]\n",
    "            leftCnt[v1] += 1 \n",
    "        res = 0\n",
    "        rightCnt = [0] * 10 \n",
    "        right = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            v1 = ord(s[i]) - ord('0')\n",
    "            leftCnt[v1] -= 1\n",
    "            for v2 in range(10):\n",
    "                left[v2][v1] -= leftCnt[v2]\n",
    "            for v2 in range(10):\n",
    "                for v3 in range(10):\n",
    "                    res += left[v2][v3] * right[v3][v2]\n",
    "                    res %= 10 ** 9 + 7 \n",
    "            for v2 in range(10):\n",
    "                right[v1][v2] += rightCnt[v2]\n",
    "            rightCnt[v1] += 1 \n",
    "        return res \n",
    "\n",
    "\n",
    "        n = len(s)\n",
    "        leftCnt = [0] * 10 \n",
    "        left = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        rightCnt = [0] * 10\n",
    "        right = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(n):\n",
    "            v1 = ord(s[i]) - ord('0')\n",
    "            for v2 in range(10):\n",
    "                left[v2][v1] += leftCnt[v2]\n",
    "            leftCnt[v1] += 1 \n",
    "        # print(left)\n",
    "        res = 0\n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            v1 = ord(s[i]) - ord('0')\n",
    "            leftCnt[v1] -= 1 \n",
    "            for v2 in range(10):\n",
    "                left[v2][v1] -= leftCnt[v2]\n",
    "            for v2 in range(10):\n",
    "                for v3 in range(10):\n",
    "                    res += left[v2][v3] * right[v3][v2]\n",
    "            for v2 in range(10):\n",
    "                right[v1][v2] += rightCnt[v2]\n",
    "            rightCnt[v1] += 1 \n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        nums = list(map(int,s))\n",
    "        n,mod = len(s),1000000007\n",
    "        r_acc = [0] * 10\n",
    "        r_cnt = [0] * 100\n",
    "        for x in nums[::-1]:\n",
    "            for y in range(10): r_cnt[x*10+y] += r_acc[y]\n",
    "            r_acc[x] += 1\n",
    "        l_acc = [0] *100\n",
    "        l_cnt = [0] * 100\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            r_acc[x] -= 1\n",
    "            for y in range(10): r_cnt[x*10+y] -= r_acc[y]\n",
    "            for y in range(100): ans = (ans + l_cnt[y]*r_cnt[y]) % mod\n",
    "            for y in range(10): l_cnt[x*10+y] += l_acc[y]\n",
    "            l_acc[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        nums = list(map(int,s))\n",
    "        n,ans,mod = len(s),0,1000000007\n",
    "        l_acc,r_acc = [0]*10, [0]*10\n",
    "        l_cnt,r_cnt = [0]*100,[0]*100\n",
    "        for x in nums[::-1]:\n",
    "            for y in range(10): r_cnt[x*10+y] += r_acc[y]\n",
    "            r_acc[x] += 1\n",
    "        for x in nums:\n",
    "            r_acc[x] -= 1\n",
    "            for y in range(10): r_cnt[x*10+y] -= r_acc[y]\n",
    "            ans = (ans + sum(l*r for l,r in zip(l_cnt,r_cnt))) % mod\n",
    "            for y in range(10): l_cnt[x*10+y] += l_acc[y]\n",
    "            l_acc[x] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "\n",
    "        for v in map(int, reversed(s)):\n",
    "            for j in range(10):\n",
    "                suf2[j +v * 10] += suf[j]\n",
    "            suf[v]+= 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0]*10\n",
    "        pre2= [0]  * 100\n",
    "        for v in map(int, s):\n",
    "            suf[v] -= 1;\n",
    "            for j in range(10):\n",
    "                suf2[j +v * 10] -= suf[j]\n",
    "            ans += sum(c1* c2 for c1, c2 in zip(pre2, suf2))\n",
    "            for j in range(10):\n",
    "                pre2[j +v * 10] += pre[j]\n",
    "            pre[v]+= 1\n",
    "        return ans % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [[0]*10 for _ in range(10)]\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d][j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [[0]*10 for _ in range(10)]\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d][j] -= c\n",
    "            for i in range(10):\n",
    "                for j in range(10):\n",
    "                    c1 = pre2[i][j]\n",
    "                    c2 = suf2[i][j]\n",
    "                    ans += c1 * c2\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d][j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n",
    "        #     ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        leftCnt = [0] * 10 \n",
    "        left = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(n):\n",
    "            v1 = int(s[i])\n",
    "            for v2 in range(10):\n",
    "                left[v2][v1] += leftCnt[v2]\n",
    "            leftCnt[v1] += 1 \n",
    "        res = 0\n",
    "        rightCnt = [0] * 10 \n",
    "        right = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for i in range(n - 1, - 1, - 1):\n",
    "            v1 = int(s[i])\n",
    "            leftCnt[v1] -= 1 \n",
    "            for v2 in range(10):\n",
    "                left[v2][v1] -= leftCnt[v2]\n",
    "            for v2 in range(10):\n",
    "                for v3 in range(10):\n",
    "                    res += left[v2][v3] * right[v3][v2]\n",
    "            for v2 in range(10):\n",
    "                right[v1][v2] += rightCnt[v2]\n",
    "            rightCnt[v1] += 1 \n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        suf = [0] * 10\n",
    "        suf2 = [0] * 100\n",
    "        for d in map(int, reversed(s)):\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] += c\n",
    "            suf[d] += 1\n",
    "\n",
    "        ans = 0\n",
    "        pre = [0] * 10\n",
    "        pre2 = [0] * 100\n",
    "        for d in map(int, s):\n",
    "            suf[d] -= 1\n",
    "            for j, c in enumerate(suf):\n",
    "                suf2[d * 10 + j] -= c  # 撤销\n",
    "            ans += sum(c1 * c2 for c1, c2 in zip(pre2, suf2))  # 枚举所有字符组合\n",
    "            for j, c in enumerate(pre):\n",
    "                pre2[d * 10 + j] += c\n",
    "            pre[d] += 1\n",
    "        return ans % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        result = 0\n",
    "        suf = [0] * 10\n",
    "        # denote the occurance of a set\n",
    "        suf2 = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        pre = [0] * 10\n",
    "        # denote the occurance of a set\n",
    "        pre2 = [[0 for _ in range(10)] for _ in range(10)]\n",
    "        for c in reversed(s):\n",
    "            for j, n in enumerate(suf):\n",
    "                # add the ocurrance of (c, j)\n",
    "                suf2[int(c)][j] += n\n",
    "            suf[int(c)] += 1\n",
    "        \n",
    "        \n",
    "        # go through the s from the begining\n",
    "        for c in s:\n",
    "            suf[int(c)] -= 1\n",
    "            # delete the current\n",
    "            for j, n in enumerate(suf):\n",
    "                suf2[int(c)][j] -= n\n",
    "            for i in range(10):\n",
    "                for j in range(10):\n",
    "                    result += pre2[i][j] * suf2[j][i]\n",
    "            # add the current into prefix\n",
    "            for j, n in enumerate(pre):\n",
    "                pre2[j][int(c)] += n\n",
    "            pre[int(c)] += 1\n",
    "        return result % (10**9 + 7)\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    前后缀 + 中心枚举\n",
    "    总体思想：\n",
    "    由于回文序列的长度是固定的，假设我们枚举所有回文序列的中心点，那么只需要知道左边两个数组成的子序列出现个数，\n",
    "    和右边两个数组成的子序列出现的个数，两个相乘就是特定中心点下的符合条件的回文子序列数目了，最后把所有的枚举\n",
    "    中心点结果相加即可\n",
    "    由于每一次是固定的两个数字组合，那么以左侧为例，定义p1[i]数字i在s中出现的次数，p2[i][j]表示前i个字符（包括第i个）\n",
    "    中出现数值j的次数\n",
    "    同理右侧的后缀也定义s1[i]、s2[i][j]\n",
    "    最后对应中心点i的所有可能回文序列就是 p2[i - 1][j] * s2[i + 1][j] j ∈ [0, 99]\n",
    "    '''\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        '''\n",
    "        由于左右两边都必须有2位数字，实际上对于前缀p2[0]来说是没有意义的，反正也不会用，直接就跳过计算了\n",
    "        '''\n",
    "        p1, p2 = [0] * 10, [[0] * 100 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            '''\n",
    "            p2的定义是前i个字符中组成j的次数，而不是必须包含第i个字符对应的数字，所以从左往右遍历是一个累加\n",
    "            的过程，需要将i - 1的所有值先赋值到i维对应数字上\n",
    "            '''\n",
    "            for j in range(100):\n",
    "                if i:\n",
    "                    p2[i][j] = p2[i - 1][j]\n",
    "            ''' \n",
    "            j的取值范围是[0, 99]，当前遍历到的是十位数，个位数是不能加上当前s[i]对应数字的，这里先把\n",
    "            p1所有的取值都算进去后，再将p1[s[i]]加一\n",
    "            ''' \n",
    "            for j in range(10):\n",
    "                p2[i][int(s[i]) * 10 + j] += p1[j]\n",
    "            \n",
    "            p1[int(s[i])] += 1\n",
    "        \n",
    "        '''\n",
    "        后缀处理基本和前缀一致，需要注意的是对于前缀'103301'是 1-> 01 -> 301 这个顺序处理的，\n",
    "        后缀为了后续计算方便，也从右到左这么处理，对于同一个下标来说p2[i]和s2[i]是完全对应的\n",
    "        '''\n",
    "        s1, s2 = [0] * 10, [[0] * 100 for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(100):\n",
    "                if i < n - 1:\n",
    "                    s2[i][j] = s2[i + 1][j]\n",
    "            \n",
    "            for j in range(10):\n",
    "                s2[i][int(s[i]) * 10 + j] += s1[j]\n",
    "            \n",
    "            s1[int(s[i])] += 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(2, n - 2):\n",
    "            for j in range(100):\n",
    "                res += p2[i - 1][j] * s2[i + 1][j]\n",
    "        \n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        mod=10**9+7\n",
    "        ans=0\n",
    "        \n",
    "        \n",
    "        pre=[[0]*100 for _ in range(n)]\n",
    "        \n",
    "        dp=[0]*10\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i:pre[i]=pre[i-1].copy()\n",
    "            for num1 in range(10):\n",
    "                pre[i][num1*10+int(s[i])]+=dp[num1]\n",
    "                # pre[i][num1*10+int(s[i])]%=mod\n",
    "            dp[int(s[i])]+=1\n",
    "        \n",
    "        \n",
    "        suf=[[0]*100 for _ in range(n)]\n",
    "        dp=[0]*10\n",
    "        \n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            if i!=n-1:\n",
    "                suf[i]=suf[i+1].copy()\n",
    "            for num2 in range(10):\n",
    "                suf[i][int(s[i])*10+num2]+=dp[num2]\n",
    "                # suf[i][int(s[i])*10+num2]%=mod\n",
    "        \n",
    "            dp[int(s[i])]+=1\n",
    "        \n",
    "        \n",
    "        for i in range(2,n-2):\n",
    "            for num1 in range(10):\n",
    "                for num2 in range(10):\n",
    "                    ans+=pre[i-1][num1*10+num2]*suf[i+1][num2*10+num1]\n",
    "                    \n",
    "                    ans%=mod\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return ans%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        def h(s):\n",
    "            res = []\n",
    "            cnt1 = [0]*10\n",
    "            cnt2 = [0]*100\n",
    "            for c in s:\n",
    "                c = int(c)\n",
    "                for i, cnt in enumerate(cnt1):\n",
    "                    if cnt:\n",
    "                        cnt2[i*10+c] += cnt\n",
    "                cnt1[c] += 1\n",
    "                res.append(cnt2[::])\n",
    "            # print(cnt1, cnt2)\n",
    "            return res\n",
    "        left = h(s)\n",
    "        right = h(s[::-1])[::-1]\n",
    "        res = 0\n",
    "        mod = 10**9+7\n",
    "        for i in range(2, n-2):\n",
    "            for j in range(100):\n",
    "                # x, y = divmod(j, 10)\n",
    "                # nj = y*10 + x\n",
    "                res += left[i-1][j]*right[i+1][j]\n",
    "                res %= mod\n",
    "        return res%mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        p1, p2 = [0] * 10, [[0] * 100 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(100):\n",
    "                if i:\n",
    "                    p2[i][j] = p2[i - 1][j]\n",
    "            \n",
    "            for j in range(10):\n",
    "                p2[i][int(s[i]) * 10 + j] += p1[j]\n",
    "            \n",
    "            p1[int(s[i])] += 1\n",
    "        \n",
    "        s1, s2 = [0] * 10, [[0] * 100 for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(100):\n",
    "                if i < n - 1:\n",
    "                    s2[i][j] = s2[i + 1][j]\n",
    "            \n",
    "            for j in range(10):\n",
    "                s2[i][int(s[i]) * 10 + j] += s1[j]\n",
    "            \n",
    "            s1[int(s[i])] += 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(2, n - 2):\n",
    "            for j in range(100):\n",
    "                res += p2[i - 1][j] * s2[i + 1][j]\n",
    "        \n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        cnt = [0] * 10\n",
    "        pos = [[[0] * 10 for _ in range(10)] for _ in range(n+1)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            pos[i] = deepcopy(pos[i+1])\n",
    "            cur = int(s[i])\n",
    "            for j in range(10):\n",
    "                pos[i][cur][j] += cnt[j]\n",
    "            cnt[cur] += 1\n",
    "        # print(pos)\n",
    "\n",
    "        ans = 0\n",
    "        cnt = [0] * 10\n",
    "        pre = [[0] * 10 for _ in range(10)]\n",
    "        for i in range(n-2):            \n",
    "            for j in range(10):\n",
    "                ans = (ans + sum(pre[j][k] * pos[i+1][j][k] for k in range(10))) % MOD\n",
    "            # print(i, ans)\n",
    "            cur = int(s[i])\n",
    "            for j in range(10):\n",
    "                pre[cur][j] += cnt[j]\n",
    "            cnt[cur] += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        mod = 10 ** 9 + 7\n",
    "        l = [[0] * 10 for _ in range(n)]\n",
    "        ld = [[0] * 100 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            tmp = int(s[i])\n",
    "            if i:\n",
    "                l[i] = l[i - 1].copy()\n",
    "                ld[i] = ld[i - 1].copy()\n",
    "            for k in range(10):\n",
    "                ld[i][10 * k + tmp] += l[i][k]\n",
    "            l[i][tmp] += 1\n",
    "            \n",
    "        r = [[0] * 10 for _ in range(n)]\n",
    "        rd = [[0] * 100 for _ in range(n)]\n",
    "        for j in range(n - 1, -1, -1):\n",
    "            tmp = int(s[j])\n",
    "            if j < n - 1:\n",
    "                r[j] = r[j + 1].copy()\n",
    "                rd[j] = rd[j + 1].copy()\n",
    "            for k in range(10):\n",
    "                rd[j][10 * k + tmp] += r[j][k]\n",
    "            r[j][tmp] += 1\n",
    "        \n",
    "        # print(l)\n",
    "        # print(r)\n",
    "        # for i in range(n):\n",
    "        #     print(ld[i])\n",
    "        # for i in range(n):\n",
    "        #     print(rd[i])\n",
    "        # print(ld, rd)\n",
    "        ans = 0\n",
    "        for i in range(2, n - 2):\n",
    "            for j in range(100):\n",
    "                ans += ld[i - 1][j] * rd[i + 1][j]\n",
    "            ans %= mod\n",
    "        return ans \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        MOD=10**9+7\n",
    "        dp=[[0 for _ in range(100)]for _ in range(n)]\n",
    "        dp2=[[0 for _ in range(100)]for _ in range(n)]\n",
    "        dp3=[[0 for _ in range(10)]for _ in range(n)]\n",
    "        dp4=[[0 for _ in range(10)]for _ in range(n)]\n",
    "        res=[0]*n\n",
    "        for i in range(1,n-1):\n",
    "            for _ in range(10):\n",
    "                dp3[i][_]=dp3[i-1][_]\n",
    "                dp4[n-1-i][_]=dp4[n-1-i+1][_]\n",
    "            dp3[i][int(s[i-1])]+=1\n",
    "            dp4[n-1-i][int(s[n-1-i+1])]+=1\n",
    "        # print(dp3,dp4)\n",
    "        for _ in range(2,n-2):\n",
    "            for i in range(10):\n",
    "                for j in range(10):\n",
    "                    dp[_][i*10+j]=dp[_-1][i*10+j]\n",
    "                    dp2[n-1-_][i*10+j]=dp2[n-1-_+1][i*10+j]\n",
    "            for i in range(10):\n",
    "                dp[_][i*10+int(s[_-1])]+=dp3[_-1][i]\n",
    "            for j in range(10):\n",
    "                dp2[n-1-_][int(s[n-1-_+1])*10+j]+=dp4[n-1-_+1][j]\n",
    "        # print(dp,dp2)\n",
    "        for _ in range(2,n-2):\n",
    "            for i in range(10):\n",
    "                for j in range(10):\n",
    "                    res[_]+=dp[_][i*10+j]*dp2[_][j*10+i]\n",
    "                    res[_]%=MOD\n",
    "        # print(res)\n",
    "        return sum(res)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        MOD=10**9+7\n",
    "        dp=[[0 for _ in range(100)]for _ in range(n)]\n",
    "        dp2=[[0 for _ in range(100)]for _ in range(n)]\n",
    "        dp3=[[0 for _ in range(10)]for _ in range(n)]\n",
    "        dp4=[[0 for _ in range(10)]for _ in range(n)]\n",
    "        res=[0]*n\n",
    "        for i in range(1,n-1):\n",
    "            for _ in range(10):\n",
    "                dp3[i][_]=dp3[i-1][_]\n",
    "                dp4[n-1-i][_]=dp4[n-1-i+1][_]\n",
    "            dp3[i][int(s[i-1])]+=1\n",
    "            dp4[n-1-i][int(s[n-1-i+1])]+=1\n",
    "        # print(dp3,dp4)\n",
    "        for _ in range(2,n-2):\n",
    "            for i in range(10):\n",
    "                for j in range(10):\n",
    "                    dp[_][i*10+j]=dp[_-1][i*10+j]\n",
    "                    dp2[n-1-_][i*10+j]=dp2[n-1-_+1][i*10+j]\n",
    "            for i in range(10):\n",
    "                dp[_][i*10+int(s[_-1])]+=dp3[_-1][i]\n",
    "            for j in range(10):\n",
    "                dp2[n-1-_][int(s[n-1-_+1])*10+j]+=dp4[n-1-_+1][j]\n",
    "        # print(dp,dp2)\n",
    "        for _ in range(2,n-2):\n",
    "            for i in range(10):\n",
    "                for j in range(10):\n",
    "                    res[_]+=dp[_][i*10+j]*dp2[_][j*10+i]\n",
    "                    res[_]%=MOD\n",
    "        # print(res)\n",
    "        return sum(res)%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        s = [int(x) for x in s]\n",
    "        n = len(s)\n",
    "        M = 10 ** 9 + 7\n",
    "        def go(s):\n",
    "            f = [[[0] * 10 for i in range(10)] for _ in range(n)]\n",
    "            cnt = [0] * 10\n",
    "            cnt[s[0]] += 1\n",
    "            for i in range(1, n):\n",
    "                now = s[i]\n",
    "                for j in range(10):\n",
    "                    for k in range(10):\n",
    "                        f[i][j][k] = f[i - 1][j][k]\n",
    "                for j in range(10):\n",
    "                    f[i][j][now] += cnt[j]\n",
    "                    f[i][j][now] %= M\n",
    "                    # if cnt[j]:\n",
    "                        # print(i, j, now, f[i][j][now])\n",
    "                cnt[now] += 1\n",
    "            return f\n",
    "        \n",
    "        \n",
    "        f = go(s)\n",
    "        g = go(s[::-1])\n",
    "        ret = 0\n",
    "        for i in range(2, n - 2):\n",
    "            for j in range(10):\n",
    "                for k in range(10):\n",
    "                    ret += f[i - 1][j][k] * g[n - i - 2][j][k]\n",
    "                    # if f[i - 1][j][k] and g[n - i - 2][j][k]:\n",
    "                        # print(i, s[i], j, k, f[i - 1][j][k], g[n - i - 2][j][k])\n",
    "                    ret %= M\n",
    "        return ret\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        pre = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]\n",
    "        suf = [[[0] * 10 for _ in range(10)] for _ in range(n + 2)]\n",
    "        t = list(map(int, s))\n",
    "        c = [0] * 10\n",
    "        for i, v in enumerate(t, 1):\n",
    "            for j in range(10):\n",
    "                for k in range(10):\n",
    "                    pre[i][j][k] = pre[i - 1][j][k]\n",
    "            for j in range(10):\n",
    "                pre[i][j][v] += c[j]\n",
    "            c[v] += 1\n",
    "        c = [0] * 10\n",
    "        for i in range(n, 0, -1):\n",
    "            v = t[i - 1]\n",
    "            for j in range(10):\n",
    "                for k in range(10):\n",
    "                    suf[i][j][k] = suf[i + 1][j][k]\n",
    "            for j in range(10):\n",
    "                suf[i][j][v] += c[j]\n",
    "            c[v] += 1\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(10):\n",
    "                for k in range(10):\n",
    "                    ans += pre[i - 1][j][k] * suf[i + 1][j][k]\n",
    "                    ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        p1, p2 = [0] * 10, [[0] * 100 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(100):\n",
    "                if i:\n",
    "                    p2[i][j] = p2[i - 1][j]\n",
    "            for j in range(10):\n",
    "               p2[i][int(s[i]) * 10 + j] += p1[j]\n",
    "            p1[int(s[i])] += 1\n",
    "        \n",
    "        s1, s2 = [0] * 10, [[0] * 100 for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(100):\n",
    "                if i < n - 1:\n",
    "                    s2[i][j] = s2[i + 1][j]\n",
    "            for j in range(10):\n",
    "                s2[i][int(s[i]) * 10 + j] += s1[j]\n",
    "            s1[int(s[i])] += 1\n",
    "        \n",
    "        print(s2)\n",
    "        res = 0\n",
    "        for i in range(2, n - 2):\n",
    "            for j in range(100):\n",
    "                res += p2[i - 1][j] * s2[i + 1][j]\n",
    "                # res += p2[i - 1][j] * s2[n - i - 2][j]\n",
    "        \n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        nums = list(map(int,s))\n",
    "        mod = 1000000007\n",
    "        n = len(s)\n",
    "        acc = [0]*10\n",
    "        l = [[0]*100 for _ in range(n)]\n",
    "        r = [[0]*100 for _ in range(n)]\n",
    "        for i,x in enumerate(nums):\n",
    "            for y in range(10): l[i][x*10+y] = acc[y]\n",
    "            acc[x] += 1\n",
    "            if i == 0: continue\n",
    "            for y in range(100): l[i][y] += l[i-1][y]\n",
    "        acc = [0] * 10\n",
    "        for i in range(n-1,-1,-1):\n",
    "            x = nums[i]\n",
    "            for y in range(10): r[i][x*10+y] = acc[y]\n",
    "            acc[x] += 1\n",
    "            if i == n-1: continue\n",
    "            for y in range(100): r[i][y] += r[i+1][y]\n",
    "        # for a,b in zip(l,r): print([(i,a[i]) for i in range(100) if a[i] != 0],[(i,b[i]) for i in range(100) if b[i] != 0])\n",
    "        ans = 0\n",
    "        for i in range(2,n-2):\n",
    "            for x in range(100):\n",
    "                ans = (ans + l[i-1][x] * r[i+1][x]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        s = [int(c) for c in s]\n",
    "        ordA = ord('a')\n",
    "        N = len(s)\n",
    "        C = [[0]*10 for _ in range(N+1)]\n",
    "        L = [[0]*100 for _ in range(N+1)]\n",
    "        R = [[0]*100 for _ in range(N+1)]\n",
    "        for i, (c, ci, li) in enumerate(zip(s, C[1:], L[1:]), 1):\n",
    "            for oc in range(10):\n",
    "                ci[oc] = C[i-1][oc] + (oc == c)\n",
    "            lastLi = L[i-1]\n",
    "            for oc in range(100):\n",
    "                x, y = divmod(oc, 10)\n",
    "                li[oc] = lastLi[oc] + (C[i-2][x] if i>=2 and s[i-2]==y else 0)\n",
    "        for i in range(N-1, -1, -1):\n",
    "            ri = R[i]\n",
    "            lastRi = R[i+1]\n",
    "            for oc in range(100):\n",
    "                x, y = divmod(oc, 10)\n",
    "                ri[oc] = lastRi[oc] + (C[-1][x] - C[i+1][x] if s[i] == y else 0)\n",
    "        res = 0\n",
    "        M = 10**9+7\n",
    "        for li, ri in zip(L[1:N], R[1:N]):\n",
    "            for oc in range(100):\n",
    "                res = (res + li[oc]*ri[oc])%M\n",
    "        return res\n",
    "        # L[i][x][y] = L[i-1][x][y] if s[i-1]!=y\n",
    "        #            = L[i-1][x][y] + C[i-1][x]\n",
    "        # R[i][y][x] = R[i+1][y][x] if s[i+1] != y\n",
    "        #              R[i+1][y][x] + C[i+1][x]\n",
    "\n",
    "\n",
    "\n",
    "        # c*26+oc  oc*26+c\n",
    "        # (oc+c)*27 - \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        n = len(s)\n",
    "        cnt = defaultdict(int)\n",
    "        left = [cnt.copy()]\n",
    "        pre = defaultdict(int)\n",
    "        for i in range(n):\n",
    "\n",
    "            for p in pre:\n",
    "                cnt[p + s[i]] += pre[p]\n",
    "\n",
    "            left.append(cnt.copy())\n",
    "            pre[s[i]] += 1\n",
    "\n",
    "        cnt = defaultdict(int)\n",
    "        right = [cnt.copy()]\n",
    "        pre = defaultdict(int)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for p in pre:\n",
    "                cnt[s[i] + p] += pre[p]\n",
    "            right.append(cnt.copy())\n",
    "            pre[s[i]] += 1\n",
    "        right.reverse()\n",
    "\n",
    "        for i in range(n):\n",
    "            for x in left[i]:\n",
    "                ans += right[i + 1][x[::-1]] * left[i][x]\n",
    "                ans %= mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        mod=10**9+7\n",
    "        l=[0]*10\n",
    "        l[ord(s[0])-ord('0')]+=1\n",
    "        lans=[[0]*100 for i in range(n)]\n",
    "        ls=[[0]*100 for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            for j in range(10):\n",
    "                lans[i][j*10+ord(s[i])-ord('0')]+=l[j]\n",
    "            for j in range(100):\n",
    "                ls[i][j]=(lans[i][j]+ls[i-1][j])%mod\n",
    "            l[ord(s[i])-ord('0')]+=1\n",
    "        r=[0]*10\n",
    "        r[ord(s[-1])-ord('0')]+=1\n",
    "        rans=[[0]*100 for i in range(n)]\n",
    "        rs=[[0]*100 for i in range(n)]\n",
    "        for i in reversed(range(n-1)):\n",
    "            for j in range(10):\n",
    "                rans[i][j*10+ord(s[i])-ord('0')]+=r[j]\n",
    "            for j in range(100):\n",
    "                rs[i][j]=(rans[i][j]+rs[i+1][j])%mod\n",
    "            r[ord(s[i])-ord('0')]+=1\n",
    "        ans=0\n",
    "        for i in range(2,n-2):\n",
    "            for j in range(100):\n",
    "                ans=(ans+ls[i-1][j]*rs[i+1][j]%mod)%mod\n",
    "                # print(i,j,ls[i-1][j],rs[i+1][j],ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        if len(s)<5:\n",
    "            return 0\n",
    "        n=len(s)\n",
    "        cnt_pre_1=Counter()\n",
    "        cnt_pre_2 = Counter()\n",
    "        pre1_ls=[0 for i in range(n)]\n",
    "        pre2_ls=[0 for i in range(n)]\n",
    "        for i in range(n):\n",
    "            cnt_pre_1[s[i]]+=1\n",
    "            pre1_ls[i]=dict(cnt_pre_1)\n",
    "            if i>0:\n",
    "                dict1=pre1_ls[i-1]\n",
    "                for key in dict1:\n",
    "                    cnt_pre_2[key+s[i]]+=dict1[key]\n",
    "                    pre2_ls[i]=dict(cnt_pre_2)\n",
    "        cnt_sub_1=Counter()\n",
    "        cnt_sub_2 = Counter()\n",
    "        sub1_ls=[0 for i in range(n)]\n",
    "        sub2_ls=[0 for i in range(n)]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            cnt_sub_1[s[i]]+=1\n",
    "            sub1_ls[i]=dict(cnt_sub_1)\n",
    "            if i<n-1:\n",
    "                dict1=sub1_ls[i+1]\n",
    "                for key in dict1:\n",
    "                    cnt_sub_2[s[i]+key]+=dict1[key]\n",
    "                    sub2_ls[i]=dict(cnt_sub_2)\n",
    "        r=0\n",
    "        for i in range(2,n-2):\n",
    "            pre2=pre2_ls[i-1]\n",
    "            sub2=sub2_ls[i+1]\n",
    "            for key in pre2:\n",
    "                if key[::-1] in sub2:\n",
    "                    r+=pre2[key]*sub2[key[::-1]]%(10**9+7)\n",
    "        return r%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        m = [int(c) for c in s]\n",
    "\n",
    "        @cache\n",
    "        def f(i, j, k):\n",
    "            if i == n:\n",
    "                return 0\n",
    "            res = 0\n",
    "            if k == 0:\n",
    "                res += f(i+1, j|(1<<m[i]),1)\n",
    "            elif k == 1:\n",
    "                res += f(i+1, j|(1<<(m[i]+10)),2)\n",
    "            elif k == 2:\n",
    "                res += f(i+1, j, 3)\n",
    "            elif k == 3:\n",
    "                if j&(1<<(m[i]+10)):\n",
    "                    res += f(i+1, j, 4)\n",
    "            elif k == 4:\n",
    "                if j&(1<<m[i]):\n",
    "                    res += 1\n",
    "            res += f(i+1, j, k)\n",
    "            return res % (10**9+7)\n",
    "        return f(0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPalindromes(self, s: str) -> int:\n",
    "        s, n = list(map(int, s)), len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i: int, mask: int, cnt: int) -> int:\n",
    "            if i == n: return 0\n",
    "            res = 0\n",
    "            if cnt == 0:\n",
    "                res += dfs(i + 1, mask | (1 << s[i]), 1)\n",
    "            elif cnt == 1:\n",
    "                res += dfs(i + 1, mask | (1 << (s[i] + 10)), 2)\n",
    "            elif cnt == 2:\n",
    "                res += dfs(i + 1, mask, 3)\n",
    "            elif cnt == 3 and (mask >> (s[i] + 10)) & 1 == 1:\n",
    "                res += dfs(i + 1, mask, 4)\n",
    "            elif cnt == 4 and mask >> s[i] & 1 == 1:\n",
    "                res += 1\n",
    "            res += dfs(i + 1, mask, cnt)\n",
    "            return res % (10 ** 9 + 7)\n",
    "\n",
    "        return dfs(0, 0, 0) \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
